With the availability of global communication networks, it is now common to ‘outsource’ some data processing tasks to external entities for a number of reasons. For example, the processing can be done at a reduced cost, or the external entity has better computational resources or better technologies.
One concern of outsourcing data processing is the inappropriate use of confidential information by the other entities. For example, it is desired to have an external entity process a large number of surveillance videos, or confidential scanned documents without having the external entity learn the content of the videos or documents. In another application, it is desired to perform complex analysis on images acquired by a cellular telephone with limited power and computational resources.
For such applications, conventional cryptography protects only the data during transport, and not the processing by another entity. One could resort to zero-knowledge techniques. However, zero-knowledge techniques are known to be computationally intensive. Applying such techniques to large data sets, such as images and video streams is impractical for low-complexity devices. For example, a single high-resolution image includes millions of bytes, for a video the images can occur at a rate of thirty frames per second or higher.
Zero-knowledge or secure multi-party computation was first described by Yao, “How to generate and exchange secrets,” Proceedings of the 27th IEEE Symposium on Foundations of Computer Science, pp. 162-167, 1986, for a specific problem. Later, that zero-knowledge technique was extended to other problems, Goldreich et al., “How to play any mental game—a completeness theorem for protocols with honest majority,” 19th ACM Symposium on the Theory of Computing, pp 218-229, 1987. However, those theoretical constructs were still too demanding to be of any practical use.
Since then, many secured methods have been described, Chang et al., “Oblivious Polynomial Evaluation and Oblivious Neural Learning,” Advances in Cryptology, Asiacrypt ′01, Lecture Notes in Computer Science Vol. 2248, pages 369-384, 2001, Clifton et al., “Tools for Privacy Preserving Distributed Data Mining,” SIGKDD Explorations, 4(2):28-34, 2002, Koller et al., “Protected Interactive 3D Graphics Via Remote Rendering,” SIGGRAPH 2004, Lindell et al., “Privacy preserving data mining,” Advances in Cryptology—Crypto 2000, LNCS 1880, 2000, Naor et al., “Oblivious Polynomial Evaluation,” Proc. of the 31st Symp. on Theory of Computer Science (STOC), pp. 245-254, May 1, 999, and Du et al., “Privacy-preserving cooperative scientific computations,” 4th IEEE Computer Security Foundations Workshop, pp. 273-282, Jun. 11, 2001. A full treatment of the problem can be found in the reference text book by Goldreich, Foundations of Cryptography, Cambridge University Press, 1998.
Secure multi-party computations are often analyzed for correctness, security, and overhead. Correctness measures how close a secure process approaches an ideal solution. Security measures the amount of information that can be gained from the multi-party exchange. Overhead is a measure of complexity and efficiency.
It is desired to provided for the secure processing of images and videos acquired by a client computer using a server computer. Furthermore, it is desired to minimize the computational resources required at the client computer.